import bisect
from typing import List


class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        size = len(arr1)

        # 去重排序arr2
        arr2 = sorted(set(arr2))

        # dp[i][j] = 通过操作j次使[0,i]成为严格递增序列时，arr1[i]的最小值
        dp = [[float("inf")] * (size + 1) for _ in range(size)]
        dp[0][0] = arr1[0]
        dp[0][1] = min(arr1[0], arr2[0])

        for i in range(1, size):
            if arr1[i - 1] < arr1[i]:
                dp[i][0] = max(dp[i - 1][0], arr1[i])
            for j in range(1, size + 1):
                # 替换当前数字
                idx = bisect.bisect_right(arr2, dp[i - 1][j - 1])
                if idx < len(arr2):
                    dp[i][j] = min(dp[i][j], arr2[idx])

                # 不替换当前数字
                if dp[i - 1][j] < arr1[i]:
                    dp[i][j] = min(dp[i][j], arr1[i])

        for i in range(size + 1):
            if dp[-1][i] != float("inf"):
                return i
        return -1


if __name__ == "__main__":
    # 1
    print(Solution().makeArrayIncreasing(arr1=[1, 5, 3, 6, 7], arr2=[1, 3, 2, 4]))

    # 2
    print(Solution().makeArrayIncreasing(arr1=[1, 5, 3, 6, 7], arr2=[4, 3, 1]))

    # -1
    print(Solution().makeArrayIncreasing(arr1=[1, 5, 3, 6, 7], arr2=[1, 6, 3, 3]))

    # 测试用例20/21 : 19
    print(Solution().makeArrayIncreasing(
        arr1=[31, 18, 1, 12, 23, 14, 25, 4, 17, 18, 29, 28, 35, 34, 19, 8, 25, 6, 35],
        arr2=[13, 10, 25, 18, 3, 8, 37, 20, 23, 12, 9, 36, 17, 22, 29, 6, 1, 12, 37, 6, 3, 14, 37, 2]))
